package done.easy_901_1000;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 993. Cousins in Binary Tree 二叉树的堂兄弟节点
 * <p>
 * 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
 * 如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
 * 我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。
 * 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。
 * <p>
 * 示例 1：
 * 1
 * / \
 * 2   3
 * /
 * 4
 * <p>
 * 输入：root = [1,2,3,4], x = 4, y = 3
 * 输出：false
 * 示例 2：
 * 1
 * / \
 * 2   3
 * \   \
 * 4   5
 * <p>
 * 输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
 * 输出：true
 * 提示：层序遍历 java
 * 2019-03-28 11:39 PM
 **/
@SuppressWarnings("all")
public class CousinsInBinaryTree {

    public boolean isCousins(TreeNode root, int x, int y) {
        // 190517 first
        return false;
    }

    @Test
    public void test() {
        /*
        // 例1. 返回 false
        TreeNode root = new TreeNode(1,
                    new TreeNode(2,
                              4),       3);
        int x = 3;
        int y = 4;
        */

        // 例2. 返回 true
        TreeNode root = new TreeNode(1,
                new TreeNode(2,
                        null, 4), new TreeNode(3,
                null, 5));
        int x = 5;
        int y = 4;
        info(isCousins(root, x, y));
    }
}





























/*
// 值和深度
Map<Integer, Integer> depth = new HashMap();
// 值和爹
Map<Integer, TreeNode> parent = new HashMap();

// 深度相同，parent不相同
public boolean isCousins(TreeNode root, int x, int y) {
    // 迭代找到所有的【爹】和【深度】
    dfs(root, null);

    // 深度一样爹不一样
    return (depth.get(x) == depth.get(y)
        && parent.get(x) != parent.get(y));
}

// 保存【值-深度】
// 保存【值-爹】
public void dfs(TreeNode node, TreeNode par) {
    if (node != null) {

        depth.put(node.val, par != null ? 1 + depth.get(par.val) : 0);
        parent.put(node.val, par);

        // 递归的写左子树、右子树
        dfs(node.left, node);
        dfs(node.right, node);
    }
}
*/
